Custom logic circuits are typically expressed as a netlist of undirected MOS devices. In such circuits, a signal often flows through a given MOS device in only one direction. For such devices, it is not necessary to analyze the possibility that signals flow in the opposite direction, thus simplifying analysis of the circuit. Determining which MOS devices have uni-directional signals can be very useful in several Electronic Design Application (EDA) applications, such as switch-level timing, fault grading, and logical abstraction of the circuit's function for equivalence checking, Automatic Test Pattern Generation (ATPG) and simulation acceleration. With logical abstraction, for example, EDA tools can represent a circuit as a graph. The nodes of this graph represent nets, and the edges represent MOS devices. The number of paths through the graph that must be examined can be greatly reduced if the direction of a signal through a MOS device is known. Several known methods are used to direct MOS devices. While these methods have been effective to some degree, they can be improved.
One known method requires a user to manually assign directions to MOS devices. Manually assigning directions, however, places unnecessary burdens on the user, and is not time and cost efficient. Further, manually assigning directions is more likely to result in direction errors, which can cause simulation tools to generate incorrect results.
Another known method is using local topological checks, which direct MOS devices according to a set of rules. For example, a rule may state “A MOS that links to grounded net A to another net B will be directed from A to B.” Systems that use rule sets, however, typically have a relatively large number of rules, e.g., about 12 rules. Further, local topology checks cannot direct many types of devices that are found in real circuits. Another shortcoming of local topographical checks is that EDA tools often use rules that are heuristic, i.e. not always correct or accurate, thus causing occasional direction errors and misdirected devices, which must be manually corrected by a user. Additionally, these methods are limited since they analyze local structures and cannot infer the direction of MOS devices based on a global circuit structure.
An additional known method of directing MOS devices is using global checks, which build a connectivity graph. The graph has a node for each net in the circuit, and each MOS device is represented as an edge between the nodes that the MOS device links. Nodes that can be driven from outside the circuit are marked as input nodes, including power and ground nets. Nodes that can drive a device outside the circuit are marked as output nodes. MOS devices are directed based on the existence of paths though the graph. A MOS device linking nets A and B and represented by edge E may drive a signal from A to B if a path in the graph starts on an input node, travels through E from A to B, and ends on an output node. Edge E can be directed if such a path exists in only one direction through E.
Global path check methods, however, can be incomplete. For example, they can leave directable devices undirected, thus resulting in wasted effort by an EDA program. Global check techniques also do not check that the paths they identify are sensitizable, i.e., there exists some input to the circuit that causes the path to conduct a signal. Therefore, these methods can fail to assign direction when a path exists through a MOS device in both directions, but all paths in one direction are not sensitized. Global check methods can also be improved to address this assignment shortcoming by checking for false paths and eliminating the identified false paths from consideration, however, such methods may not be accurate when the circuit is a dynamic circuit that includes pre-charged nets.
Other known methods combine local topology checks with global path checks. Such methods, however, fail to provide a complete system, and may nevertheless require a user to manually assign directions.
Accordingly, there exists a need for a method for directing MOS devices so that circuit analysis is simplified, more time and cost efficient, and more accurate. There also exists a need for a method that eliminates false positives in direction assignment and ensures that direction assignments are safe for all input conditions. Further, the method should detect false paths and be applicable to a wider range of circuits without requiring a user to manually assign devices or correct direction assignments. Methods should also be applicable to both static and dynamic circuits.
Embodiments of the invention fulfill these unmet needs.